Optimization scheme for sensor coverage scheduling with bandwidth constraints

Wireless Sensor Network has attracted a lot of attentions due to its broad applications in recent years and also introduces many challenges. Network lifetime is a critical issue in Wireless Sensor Networks. It is possible to extend network lifetime by organizing the sensors into a number of sensor covers. However, with the limited bandwidth, coverage breach (i.e, targets that are not covered) can occur if the number of available time-slots/channels is less than the number of sensors in a sensor cover. In this paper, we study a joint optimization problem in which the objective is to minimize the coverage breach as well as to maximize the network lifetime. We show a “trade-off” scheme by presenting two strongly related models, which aim to tradeoffs between the two conflicting objectives. The main approach of our models is organizing sensors into non-disjoint sets, which is different from the current most popular approach and can gain longer network lifetime as well as less coverage breach. We proposed two algorithms for the first model based on linear programming and greedy techniques, respectively. Then we transform these algorithms to solve the second model by revealing the strong connection between the models. Through numerical simulation, we showed the good performance of our algorithms and the pictures of the tradeoff scheme in variant scenarios, which coincide with theoretical analysis very well. It is also showed that our algorithms could obtain less breach rate than the one proposed in (Cheng et al. in INFOCOM’ 05, 2005).     

局部对称共形平坦黎曼流形中紧致极小子流形的一个刚性定理

本文研究局部对称共形平坦黎曼流形中紧致极小子流形,得到了这类子流形第二基本形式模长平方关于外围空间Ricci曲率的—个拼挤定理,推广了文[1]中的结果.     

The heat kernel and Hardy’s theorem on symmetric spaces of noncompact type

For symmetric spaces of noncompact type we prove an analogue of Hardy’s theorem which characterizes the heat kernel in terms of its order of magnitude and that of its Fourier transform.     

一类优美图

设u、ν是两个固定顶点.用b条内部互不相交且长度皆为a的道路连接u、ν所得的图用P_a,b表示.KM.Kathiresan证实P_2,2m-1(r,m皆为任意正整数)是优美的,且猜想:除了(a,b)=(2r+1,4s+2)外,所有的P_a,b都是优美的.杨元生已证实P_2r+1,2m-1是优美的,并且证实了当r=1,2,3,4时的P_2r,2m也是优美的.本文证实r=5,6,7时P_{2r,2m相似文献}   

Bin packing can be solved within 1 + ε in linear time

For any listL ofn numbers in (0, 1) letL* denote the minimum number of unit capacity bins needed to pack the elements ofL. We prove that, for every positive ε, there exists anO(n)-time algorithmS such that, ifS(L) denotes the number of bins used byS forL, thenS(L)/L*≦1+ε for anyL providedL* is sufficiently large. The work of this author was supported by NSF Grant MCS 70-04997.     

关于Davenport常数的一些估计

本文就Ｇ为幂零群或Ｇ可写成两个子群之直和的情形，给Ｇ的Ｄａｖｅｎｐｏｒｔ常数Ｄ（Ｇ）一些非平凡的估计．     

关于n阶微分方程边值问题（Ⅲ）——奇摄动的渐近展开

本文研究n阶非线性过值问题(NB)的奇异摄动。在较一般的条件下,应用高阶微分不等式理论证明了摄动解的存在性,并给出了摄动解直到n阶导函数的一致有效渐近展开式,推广和改进了已有的结果。     

Mathematical Models for Studying the Value of Motivational Leadership in Teams

Mathematical models are presented for studying the value of leadership in a team where the members interact with each other. The models are based on a leader’s role of motivating each team member to perform closer to his/her maximum ability. These models include controllable parameters whose values reflect the amount of task interdependence among the workers as well as the motivational skill and variability in the skill of the leader. Confirming results—such as the fact that the skill level of the leader is a critical factor in the expected performance of the team—establish credibility in the models. Mathematical analysis and computer simulations are used to provide new managerial insights into the value of the leader—such as the fact that the skill of the leader can be more important than controlling the amount of interdependence among the team members and that having a choice of multiple leaders with no particular motivating skill is beneficial to the performance of small teams but not to large teams.Daniel Solow received a B.S. in Mathematics from Carnegie-Mellon, an M.S. in Operations Research from the University of California at Berkeley, and a Ph. D. in Operations Research from Stanford University. He has been a professor at Case Western Reserve University since 1978. His research interests include complex systems, discrete, linear, and nonlinear optimization. He has also developed systematic methods for teaching mathematical proofs, computer programming, and operations research.Sandy Kristin Piderit is an assistant professor of organizational behavior at the Weatherhead School of Management at Case Western Reserve University, and earned her Ph.D. from the University of Michigan. She studies the roles of relationships among coworkers on their performance and satisfaction with their work environments, and has published studies in the Academy of Management Review, the Journal of Management Studies, and Management Science.Apostolos Burnetas received a Diploma in Electrical Engineering from National Technical University in Athens, Greece, and an M.B.A. and Ph.D. in Operations Research from Rutgers University. He has been at the Department of Operations at Case Western Reserve University and is currently an Associate Professor at the Department of Mathematics at the University of Athens. His research interests include stochastic models and optimization, complex systems, and applications in queueing systems, supply chain and the interface of operations with finance.Chartchai Leenawong received a B.S. in Mathematics from Chulalongkorn University in Bangkok, an M.S. in Computer Science from the Asian Institute of Technology in Bangkok, and a Ph.D. in Operations Research from Case Western Reserve University. His research interests include mathematical modeling of complex systems as applied to business organizations. He has been a professor at King Mongkut’s Institute of Technology Ladkrabang, Bangkok, Thailand since 2002.     

Graph bisection algorithms with good average case behavior

In the paper, we describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixedd≧3, all sufficiently largen and allb=o(n ^{1?1/[(d+1)/2]}), the algorithm finds the minimum bisection for almost alld-regular labelled simple graphs with 2n nodes and bisection widthb. For example, the algorithm succeeds for almost all 5-regular graphs with 2n nodes and bisection widtho(n ^2/3). The algorithm differs from other graph bisection heuristics (as well as from many heuristics for other NP-complete problems) in several respects. Most notably:

1. the algorithm provides exactly the minimum bisection for almost all input graphs with the specified form, instead of only an approximation of the minimum bisection,
2. whenever the algorithm produces a bisection, it is guaranteed to be optimal (i.e., the algorithm also produces a proof that the bisection it outputs is an optimal bisection),
3. the algorithm works well both theoretically and experimentally,
4. the algorithm employs global methods such as network flow instead of local operations such as 2-changes, and
5. the algorithm works well for graphs with small bisections (as opposed to graphs with large bisections, for which arbitrary bisections are nearly optimal).

     

The complexity of a class of infinite graphs

IfG _k is the family of countable graphs with nok vertex (or edge) disjoint circuits (1<k<) then there is a countableG _k G _k such that every member ofG _k is an (induced) subgraph of some member ofG _k , but no finiteG _k suffices.